perm filename IDEAS[W82,JMC]1 blob sn#640283 filedate 1982-02-07 generic text, type C, neo UTF8
COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	ideas[w82,jmc]		string search
C00007 ENDMK
C⊗;
ideas[w82,jmc]		string search

∂23-Jan-82  2316	JMC  	improved string search  
To:   cl.boyer at UTEXAS-20, cl.moore at UTEXAS-20   
Here is an "improvement" on your string search whose correctness statement
might be difficult to formalize.  The algorithm is essentially that given
in your book, except for a change in the initialization to avoid updating
the table for all letters of the alphabet.  Each entry in the table includes
your (DELTA1 K) in its low order bits and an integer <search number> in its
high order bits.  When we start a new search, we update the entries
corresponding to the letters in the pattern string but with a search number
one larger than that of the last search.  We don't bother changing the
entries for letters that don't appear in the pattern string, because a
simple comparison when the letter is encountered in the text shows that
the entry is obsolete.  Only when the search number threatens to overflow
the allocated field do we go through the entire table and restart with
search number 1.

Since I don't know the literature and couldn't find a reference to this
kind of searching in Knuth vols. 1-3, this may be an old idea.

Notice that stating the correctness and the efficiency of the algorithm
requires taking into account that the algorithm may be used many times.

Jan 27
	The California condor is dying out because it requires human carrion.

Jan 27
	Carolyn points out the existence of partial reflection principles
and partial self confidence principles.  true(n,p) ≡ p for expressions
p of quantifier depth ≤ n.  An analogous scheme would get around
Montague's paradoxes of knowledge.

Feb 7
	Mappings into some other entities than linear groups might get
around the problem that non-commutative non-compact groups require
infinite dimensional representations for completeness.  Mappings into
and out of the groups need to be inter-related.

Feb 7
	The ideas in my MULTIP[1,JMC]@S1 are probably not adequate
for programming subroutines.  Consider a matrix multiplication
subroutine.  Which parts are done in parallel and how much
parallelism is allowed needs to depend on the size of the matrices
in a more flexible way than I have allowed.

Feb 7
	A modest proposal for treachery.  We give the Chinese communists
Taiwan which gets them doubling their foreign trade, nuclear reactors,
a shipbuilding industry, etc.  They can try to control it by exchanging
populations.  The social scientists get to study whether they can
maintain its productivity.  They conquer Indochina for us.